/**
 * @author 雷明浩
 * @date 2025/6/26 16:13
 */
public class LowestBinarySearchAncestor {
    // 二叉搜索树的最近公共祖先
    // https://www.nowcoder.com/practice/d9820119321945f588ed6a26f0a6991f?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D295

    /**
     * 因为是二叉搜索树，所以一次可以排除一半的节点
     * @param root
     * @param p
     * @param q
     * @return
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        if (root == null) {
            return -1;
        }
        if (root.val == p || root.val == q) {
            return root.val;
        }
        int min = Math.min(p, q);
        int max = Math.max(p, q);
        if (root.val > min && root.val < max) {
            return root.val;
        } else if (root.val > max) {
            return lowestCommonAncestor(root.left, p, q);
        } else {
            return lowestCommonAncestor(root.right, p, q);
        }
    }
}